#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "kernel/fs.h"

int strncmp(const char *p, const char *q, uint n)
{
  while(n > 0 && *p && *p == *q)
    n--, p++, q++;
  if(n == 0)
    return 0;
  return (uchar)*p - (uchar)*q;
}

int match(const char *pattern, const char *name) {
    int pattern_len = strlen(pattern);
    int name_len = strlen(name);

    if (pattern[0] == '*' && pattern[pattern_len - 1] == '*') {
        if (pattern_len > 2) {
            char sub[DIRSIZ];
            int sub_len = pattern_len - 2;
            memmove(sub, pattern + 1, sub_len);
            sub[sub_len] = 0;
            
            if (strlen(name) < sub_len) {
                return 0;
            }

            for (int i = 0; i <= name_len - sub_len; i++) {
                if (strncmp(name + i, sub, sub_len) == 0) {
                    return 1;
                }
            }
            return 0;
        }
        return 1;
    } else if (pattern[0] == '*') {
        if (name_len >= pattern_len - 1) {
            return strcmp(name + name_len - (pattern_len - 1), pattern + 1) == 0;
        }
    } else if (pattern[pattern_len - 1] == '*') {
        return strncmp(name, pattern, pattern_len - 1) == 0;
    }
    return strcmp(name, pattern) == 0;
}

void find(char *path, const char *pattern) {
    char buf[512], *p;
    int fd;
    struct dirent de;
    struct stat st;

    if ((fd = open(path, 0)) < 0) {
        fprintf(2, "findx: cannot open %s\n", path);
        return;
    }

    if (fstat(fd, &st) < 0) {
        fprintf(2, "findx: cannot stat %s\n", path);
        close(fd);
        return;
    }

    switch (st.type) {
        case T_FILE:
            if (match(pattern, path)) {
                printf("%s\n", path);
            }
            break;

        case T_DIR:
            if (strlen(path) + 1 + DIRSIZ + 1 > sizeof buf) {
                printf("findx: path too long\n");
                break;
            }
            strcpy(buf, path);
            p = buf + strlen(buf);
            *p++ = '/';
            while (read(fd, &de, sizeof(de)) == sizeof(de)) {
                if (de.inum == 0)
                    continue;
                
                // Skip . and ..
                if (strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0)
                    continue;

                memmove(p, de.name, DIRSIZ);
                p[DIRSIZ] = 0;
                if (stat(buf, &st) < 0) {
                    printf("findx: cannot stat %s\n", buf);
                    continue;
                }

                if (st.type == T_DIR) {
                    find(buf, pattern);
                } else if (st.type == T_FILE) {
                    if (match(pattern, de.name)) {
                        printf("%s\n", buf);
                    }
                }
            }
            break;
    }
    close(fd);
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(2, "Usage: findx <directory> <pattern>\n");
        exit();
    }
    find(argv[1], argv[2]);
    exit();
}